package com.lagou.algorithmus;

import com.lagou.algorithmus.data.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树
 */
public class AlgorithmusTree {

    /**
     * 遍历根节点
     * 遍历根节点的左节点（如果左节点不是叶子节点，则以当前节点开始，重新从第一步开始）
     * 遍历根节点的右节点（如果右节点不是叶子节点，则以当前节点开始，重新从第一步开始）
     */
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        TreeNode treeNode = buildTree(nums, 0);
        System.out.println(treeNode);

    }

    // 递归构建二叉树
    public static TreeNode buildTree(int[] nums, int startIndex) {
        if (nums == null || startIndex >= nums.length) {
            return null;
        }
        TreeNode treeNode = new TreeNode(nums[startIndex]);
        treeNode.left = buildTree(nums, 2 * startIndex + 1);
        treeNode.right = buildTree(nums, 2 * startIndex + 2);
        return treeNode;
    }


    public static TreeNode arrayToTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        TreeNode root = constructTree(nums, 0);
        return root;
    }

    private static TreeNode constructTree(int[] nums, int index) {
        if (index >= nums.length) {
            return null;
        }
        TreeNode node = new TreeNode(nums[index]);
        node.left = constructTree(nums, 2 * index + 1);
        node.right = constructTree(nums, 2 * index + 2);
        return node;
    }

    // 左根右遍历
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        handle(root, result);
        System.out.println(result);
        return result;
    }

    public static void handle(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        handle(root.left, result);
        result.add(root.val);
        handle(root.right, result);
    }

    // 根左右 遍历
    public static void treePre(TreeNode root) {
        if (null == root) {
            return;
        }
        System.out.println(root.val);
        treePre(root.left);
        treePre(root.right);
    }

    // 左根右遍历
    public static void treeMid(TreeNode root) {
        if (null == root) {
            return;
        }
        treeMid(root.left);
        System.out.println(root.val);
        treeMid(root.right);
    }

    // 左右根
    public static void treeEnd(TreeNode root) {
        if (null == root) {
            return;
        }
        treeEnd(root.left);
        treeEnd(root.right);
        System.out.println(root.val);
    }

}
